package 数据结构设计高频题;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 插入、删除和获取随机元素O(1)时间且允许有重复数字的结构
// 测试链接 :
// https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/
public class Code04_InsertDeleteRandomDuplicatesAllowed {

    class RandomizedCollection {
        private HashMap<Integer, HashSet<Integer>> value_SetMap;
        private ArrayList<Integer> arr;

        public RandomizedCollection() {
            value_SetMap = new HashMap<>();
            arr = new ArrayList<>();
        }

        public boolean insert(int val) {
            arr.add(val);
            HashSet<Integer> set = value_SetMap.getOrDefault(val, new HashSet<Integer>());
            set.add(arr.size() - 1);
            value_SetMap.put(val, set);
            return set.size() == 1;
        }

        public boolean remove(int val) {
            if(!value_SetMap.containsKey(val)){
                return false;
            }
            HashSet<Integer> indexSet = value_SetMap.get(val);
            int anyIndex = indexSet.iterator().next();
            int endValue = arr.get(arr.size() - 1);
            if(val == endValue){
                indexSet.remove(arr.size() - 1);
            }else{
                arr.set(anyIndex, endValue);
                HashSet<Integer> endValueSet = value_SetMap.get(endValue);
                endValueSet.add(anyIndex);
                endValueSet.remove(arr.size() - 1);
                indexSet.remove(anyIndex);
            }
            arr.remove(arr.size() - 1);
            if(indexSet.isEmpty()){
                value_SetMap.remove(val);
            }
            return true;
        }

        public int getRandom() {
            return arr.get((int) (Math.random() * arr.size()));
        }
    }
}
